package com.tgy.programmer_code_interview_guide._03_binarytree;

import java.util.*;

public class _22_通过先序和中序生成后续遍历 {

    public static int[] postorderByPreorderAndInorder(int[] preorder, int[] inorder) {

        List<Integer> arrayList = new ArrayList<>();

        Map<Integer,Integer> map = new HashMap<>();

        for (int i = 0; i < inorder.length; i++) {

            map.put(inorder[i],i);
        }

        traversal(preorder,0,preorder.length - 1,inorder,0,inorder.length - 1,map,arrayList);



        return arrayList.stream().mapToInt(Integer::valueOf).toArray();
    }

    private static void traversal(int[] preorder, int p1, int p2, int[] inorder, int i1, int i2,Map<Integer,Integer> map, List<Integer> res) {

        if (p1 > p2) {

            return;
        }

        int val = preorder[p1];
        int len = map.get(val) - i1;
        traversal(preorder,p1+1,p1 + len,inorder,i1,i1+len - 1 , map,res);
        traversal(preorder,p1+len + 1,p2,inorder,i1+len+1,i2,map,res);
        res.add(val);
    }

    public static void main(String[] args) {

        int[] preorders = {1,2,4,5,8,9,3,6,7};
        int[] inorders = {4,2,8,5,9,1,6,3,7};

        int[] ints = postorderByPreorderAndInorder(preorders, inorders);
        System.out.println(Arrays.toString(ints));
    }
}
